import sortedcontainers
class Solution(object):
    def countRangeSum(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        prefix = nums.copy()
        n = len(nums)
        stack = sortedcontainers.SortedList()
        stack.add(0)
        for i in range(1, n):
            prefix[i] += prefix[i - 1]
        total = 0
        for i in range(n):
            upper_num = prefix[i] - lower
            lower_num = prefix[i] - upper
            right_index = stack.bisect_right(upper_num)
            left_index = stack.bisect_left(lower_num)
            total += right_index - left_index
            stack.add(prefix[i])
        return total

data = Solution()
nums = [-2, 5, -1]
lower = -2
upper = 2
print(data.countRangeSum(nums, lower, upper))
nums = [-1, 1]
lower = 0
upper = 0
print(data.countRangeSum(nums, lower, upper))